/*
 * BitLinked.h
 *
 *  Created on: 27/08/2012
 *      Author: marciocs5
 */

#ifndef BITLINKED_H_
#define BITLINKED_H_

#include "BitTools.h"
#include <stdlib.h>
#include <stdio.h>
/*
 *	Estrutura de dados que é um vetor de bits encadeado(???).
 *
 *	A estrutura representa um conjunto. Os elementos são armazenados
 *	em no vetor vector como um vetor caracteristico.
 *
 *	ant e prox indicam respectivamente a ultima palavra não-nula e a primeira
 *	não-nula posterior a cada palavra. Ou seja, se ant[i] = j então vector[j] !=
 *	0 e vector[j+1]= vector[j+2] = ... = vector[i-1] = 0 e analogamente para
 *	prox.
 *
 * */
template<typename T>
class BitVector {
private:
	T* vector;// vetor de bits
	long* ant;// lista de predecessores
	long* prox;// lista de sucessores
	long vectorsz;// tamanho do vetor
	long logw;// log do tamanho da palavra
	long sizew;// tamanho da palavra
	long mask;
	long n;// numero de bits

	// atualiza a lista colocando o nó vector[i] nela
	void putIn(long i);

	// atualiza a lista retirando o nó vector[i] dela
	void takeOut(long i);

protected:
	// determina dentro da palavra qual o deslocamento para o bit i
	long inWordIdx(long i);

	// determina a palavra em que o bit i esta
	long wordIdx(long i);

	// determina dentro da palavra idx, o proximo bit 1 depois de i
	long leastBit(long i, long idx);

	//conta no numero de bits 1 na palavra idx
	long countBit(long idx);

public:
	//construtor
	BitVector(long n);

	//destrutor
	virtual ~BitVector();

	//numero de bits
	virtual long size();

	//tamanho do vetor de bits
	virtual long sizeInWord();

	//coloca um bit no conjunto
	virtual void toSet(long i);

	//retira um bit do conjunto
	virtual void toCompl(long i);

	//coloca todos os bits no conjunto
	virtual void allToSet();

	//retira todos os vertices do conjunto
	virtual void allToCompl();

	//verifica se um vertice esta no conjunto
	virtual bool isInSet(long i);

	//OU
	virtual void logicor(BitVector<T>* v);

	//E
	virtual void logicand(BitVector<T>* v);

	//NÃO
	virtual void logicneg();

	//numero de bits setados no conjunto
	virtual long cardOfset();

	//verifica se o conjunto é vazio
	virtual bool isEmpty();

	//next bit no conjuto segundo sua ordem natural
	virtual long nextSet(long i);

	//for debug
	virtual void show();
};

template<typename T>
inline void BitVector<T>::putIn(long i){
	long anti = ant[i];
	long proxi = prox[i];
	for(long j = anti; j < i; j++)	prox[j] = i;
	for(long j = i + 1; j <= proxi; j++)ant[j] = i;
}

template<typename T>
inline void BitVector<T>::takeOut(long i){
	long anti = ant[i];
	long proxi = prox[i];
	for(long j = anti; j < i; j++)prox[j] = proxi;
	for(long j = i + 1; j <= proxi; j++)ant[j] = anti;
}

template<typename T>
BitVector<T>::BitVector(long n){
	this->n = n;
	logw = inline_ceillog(sizeof(T), 1) + 3;
	sizew = sizeof(T);
	mask = (1LL << logw) - 1;
	vectorsz = (n >> logw) + 1;
	vector = new T[vectorsz];
	ant = new long[vectorsz];
	prox = new long[vectorsz];
	for(long i = 0; i < vectorsz; i++){
		prox[i] = vectorsz-1;
		ant[i] = 0;
		vector[i] = 0;
	}
}

template<typename T>
BitVector<T>::~BitVector(){
	delete vector;
	delete ant;
	delete prox;
}

template<typename T>
inline long BitVector<T>::inWordIdx(long i){
	return i & mask;
}

template<typename T>
inline long BitVector<T>::wordIdx(long i){
	return i >> logw;
}

template<>
inline long BitVector<int>::leastBit(long i, long idx){
	return builtinLeast<int>(vector[idx] & posmasksimp[i]);
}

template<>
inline long BitVector<long>::leastBit(long i, long idx){
	return builtinLeast<long>(vector[idx] & posmasklsimp[i]);
}

template<typename T>
inline long BitVector<T>::countBit(long idx){
	return builtinCounter<T>(vector[idx]);
}

template<typename T>
inline long BitVector<T>::size(){
	return n;
}

template<typename T>
inline long BitVector<T>::sizeInWord(){
	return vectorsz;
}

template<typename T>
inline void BitVector<T>::toSet(long i){
	if(vector[wordIdx(i)] != 0)vector[wordIdx(i)] |= (1LL << (inWordIdx(i)));
	else{
		vector[wordIdx(i)] |= (1LL << (inWordIdx(i)));
		putIn(wordIdx(i));
	}
}

template<typename T>
inline void BitVector<T>::toCompl(long i){
	vector[wordIdx(i)] &= ~(1LL << (inWordIdx(i)));
	if(vector[wordIdx(i)] == 0){
		takeOut(wordIdx(i));
	}
}

template<typename T>
inline void BitVector<T>::allToSet(){
	for(long i = 1; i < vectorsz-1; i++){
		vector[i] = ~(0LL);
		ant[i] = i-1;
		prox[i] = i+1;
	}
	vector[0] = ~(0LL);
	ant[0] = 0;
	prox[0] = 1;
	vector[vectorsz-1] = ~(0LL);
	ant[vectorsz - 1] = vectorsz - 2 < 0 ? 0 : vectorsz - 2 ;
	prox[vectorsz -1] = vectorsz - 1;
}

template<typename T>
inline void BitVector<T>::allToCompl(){
	for(long i = 0; i < vectorsz; i++){
		vector[i] = 0;
		ant[i] = 0;
		prox[i] = vectorsz -1;
	}
}

template<typename T>
inline bool BitVector<T>::isInSet(long i){
	return (vector[wordIdx(i)] & (1LL << (inWordIdx(i)))) != 0;
}

template<typename T>
inline void BitVector<T>::logicor(BitVector<T>* v){
	long index = 0;
	if(v->vector[0] != 0){
		vector[0] |= v->vector[0];
		putIn(0);
	}
	index = v->prox[index];
	while(index < (vectorsz -1)){
		vector[index] |= v->vector[index];
		putIn(index);
		index = v->prox[index];
	}
	if(v->vector[vectorsz-1] != 0){
		vector[vectorsz-1] |= v->vector[vectorsz-1];
		putIn(vectorsz-1);
	}
}

template<typename T>
inline void BitVector<T>::logicand(BitVector<T>* v){
	long index = 0;
	if(vector[0] != 0){
		vector[0] &= v->vector[0];
		if(vector[0] == 0)takeOut(0);
	}
	index = prox[index];
	while(index < (vectorsz -1)){
		vector[index] &= v->vector[index];
		if(vector[index] == 0)takeOut(index);
		index = prox[index];
	}
	if(vector[vectorsz-1] != 0){
		vector[vectorsz-1] &= v->vector[vectorsz-1];
		if(vector[index] == 0)takeOut(vectorsz-1);
	}
}

template<typename T>
inline void BitVector<T>::logicneg(){
	for(long i = 0; i < vectorsz; i++){
		if(vector[i] == 0) putIn(i);
		if(vector[i] == (~0)) takeOut(i);
		vector[i] = ~vector[i];
	}
}

template<typename T>
inline long BitVector<T>::cardOfset(){
	long index = 0;
	long count = 0;
	while(index < (vectorsz - 1)){
		count += countBit(index);
		index = prox[index];
	}
	count += countBit(vectorsz - 1);
	return 0;
}

template<typename T>
inline bool BitVector<T>::isEmpty(){
	if(leastBit(0,0) != -1) return false;
	if(leastBit(0,(vectorsz-1)) != -1) return false;
	return prox[0] == (vectorsz -1);
}

template<typename T>
inline long BitVector<T>::nextSet(long i){
	long index = wordIdx(i);
	long ret = leastBit(inWordIdx(i), index);
	if(ret == -1){
		index = prox[index];
		ret = leastBit(0,index);
		if(ret == -1) return -1;
	}
	return ret + (index << logw);
}

template<typename T>
inline void BitVector<T>::show(){
	printf("\n Estrutura!\n");
	printf("vetor de base! \n");
	for(long i = 0; i < size()-1; i++){
		if(isInSet(i))printf("<%lu>", i);
	}
	printf("\n vetor de ant \n");
	for(long i = 0; i < sizeInWord()-1; i++){
		printf("%lu -> <%lu> |", i, ant[i]);
	}
	printf("\n vetor de prox \n");
	for(long i = 0; i < sizeInWord()-1; i++){
		printf("%lu -> <%lu> |", i, prox[i]);
	}
	printf("\n");
}

#endif /* BITLINKED_H_ */
